package SortAlgorithm;

import java.text.SimpleDateFormat;
import java.util.Date;

/**
 * @Classname ShellSort  简单排序效率不高； 希尔排序 也是插入排序 缩小增量排序
 * @Description TODO
 * @Date 2021/11/10 16:10
 * @Created leiyuee
 */
public class ShellSort {

    public static void main(String[] args) {
//        int[] arr = new int[80000];
//        for (int i = 0; i < 80000; i++) {
//            arr[i] = (int) (Math.random() * 8000000);
//        }
        int[] arr = {8,9,1,7,2,3,5,4,6,0};
        Date date = new Date();
        SimpleDateFormat simpleDateFormat = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format = simpleDateFormat.format(date);
        System.out.println("排序前：" + format);
        shellSort(arr); //交换
        shellSort2(arr);//移位
        Date date2 = new Date();
        SimpleDateFormat simpleDateFormat2 = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss");
        String format2 = simpleDateFormat2.format(date2);
        System.out.println("排序后：" + format2);
    }
    //对有序序列再插入时采用交换法
    public static void shellSort(int[] arr) {
        int temp = 0;
        int count = 0;
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                for (int j = i - gap; j >= 0; j -= gap) {
                    if (arr[j]>arr[j+gap]){
                        temp=arr[j];
                        arr[j] = arr[j+gap];
                        arr[j+gap] = temp;
                    }
                }
            }
        }
    }

    //对有序序列再插入时采用交换法
    public static void shellSort2(int[] arr) {
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            for (int i = gap; i < arr.length; i++) {
                int j=i;
                int temp = arr[j];
                if (arr[j]<arr[j-gap]){
                    arr[j] = arr[j-gap];
                    j-=gap;
                }
                arr[i] =temp;
            }
        }
    }
}